#include <cstdio>
#include <cstring>
#include "Stack.h"
#include "Queue.h"
#include "dfs.h"

extern const int directX[4], directY[4];
//extern const int directX[4] = {-1, 0, 1, 0}, directY[4] = {0, 1, 0, -1};
using namespace std;

void print_path_bfs(Coord<int> start, Coord<int> end, Map<Coord<int> > &last)
{
    Stack<Coord<int> > path;
    Coord<int> curr = end;
    int tempx = curr.x();
    while (!(curr == start)) {
        path.push(curr);
        curr.x(last.val(curr.y(), curr.x()).x());
        curr.y(last.val(curr.y(), tempx).y());
        tempx = curr.x();
    }
    path.push(start);
    print_path_dfs(path);
}

bool bfs(Coord<int> const &start,
         Coord<int> const &end,
         Queue<Coord<int> > &queue,
         Map<int> &visited,
         Map<int> const &maze)
{
    bool success = false;

    Map<Coord<int> > last(maze.cols(), maze.rows());
    last.emplace(0);

    queue.push(start);

    while (!queue.empty()) {
        Coord<int> curr = queue.head();
        if (curr == end) {
            print_path_bfs(start, end, last);
            success = true;
            break;
        }
        queue.pop();
        visited.val(curr.y(), curr.x(), 1);
        for (int i = 0; i < 4; i++) {
            int x = curr.x() + directX[i], y = curr.y() + directY[i];
            if (x < 0 || x >= maze.rows() || y < 0 || y >= maze.cols())
                continue;
            if (maze.val(y, x) || visited.val(y, x))
                continue;

            queue.push({x, y});
//            last_x[x][y] = cx;
//            last_y[x][y] = cy;

            last.val(y, x, {curr.x(), curr.y()});
        }
    }
    if (!success)
        puts("There is no path .\n");

    return success;
}